package Algorithm.sort.basic;

import utils.CommonUtils;

import java.util.Arrays;

/**
 * 选择排序：遍历整个序列选出最小的元素与第一个元素交换位置，这样就确定了一个元素的位置，然后继续从剩余元素选出最小元素，以此类推，最后选出来的序列就是有序序列了
 *
 * 优化：在寻找最小元素时顺便检查数组是否已经按序排列，及时终止排序。寻找最小元素要从表尾对比到表头，寻找最大元素则从表头对比到表尾，若这个过程中每次对比当前最小（大）元素的位置都发生了改变，则说明数组已经有序
 *
 * 简单选择排序性能：时间复杂度平均O(n2)，最好O(n2)，最坏O(n2)。空间复杂度O(1)。不稳定
 */
public class SelectSort {

    public static void main(String[] args) {
        int[] A = new int[]{1,2,3,3,6,9};
        selectSort2(A);
        System.out.println(Arrays.toString(A));
    }

    static void selectSort(int[] A) {
        int n = A.length;
        for(int i = 0;i < n;i++) {
            int min = i;  //记录最小元素位置
            for(int j = i+1;j < n;j++) {
                if(A[j] < A[min])
                    min = j;  //更新最小元素位置
            }
            if(min != i)
                CommonUtils.swap(A, i, min); //交换
        }
    }

    static void selectSort2(int A[]) {
        int n = A.length;
        for(int i = 0;i < n;i++) {
            int min = n-1; //记录最小元素位置
            boolean sorted = true;
            for(int j = n-2;j >= i;j--) {
                //这里如果相等也要更新位置，便于数组包含重复元素但已有序时及时终止排序
                if(A[j] <= A[min]) {
                    min = j; //更新最小元素位置
                } else {
                    sorted = false;
                }
            }
            //若从尾至头每一次比较都更新了最小元素的位置（即sorted没有被赋值false）
            //则数组已经有序
            if (sorted) return;
            if(min != i)
                CommonUtils.swap(A, i, min);
        }
    }

}
